/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/swap-two-nodes-in-linked-list
   @Language: C++
   @Datetime: 17-04-08 21:25
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
	/**
	 * @param head a ListNode
	 * @oaram v1 an integer
	 * @param v2 an integer
	 * @return a new head of singly-linked list
	 * Tip : find v1 and v2 pointers' prev: p1 , p2
	 *       get v1 and v2 pointers : a1 , a2
	 *       exchange them, especially v1 and v2 are neighbors
	 */
	ListNode* swapNodes(ListNode* h, int v1, int v2) {
		// Write your code here
		if (v1==v2) return h;
		ListNode H(-1), *p1=NULL, *p2=NULL, *a1, *a2;
		for(H.next=h,h=&H; (!p1 || !p2) && h->next; h=h->next){
			// confirm p1 link to first vals in (v1, v2)
			if (h->next->val==v1) (p1 ? p2=h : p1=h);
			if (h->next->val==v2) (p1 ? p2=h : p1=h);
		}
		if(!p1 || !p2) return H.next;
		a1 = p1->next;
		p1->next = a2 = p2->next;
		p2!=a1 ? p2->next=a1 : p1=a1;	// v1, v2 are neighbors
		p1!=a1 ? p1=a1->next : 0;		// v1, v2 are neighbors
		p2 = a2->next;
		a1->next = p2;
		a2->next = p1;
		return H.next;
	}
};
